#include <iostream>
using namespace std;
#include <string>
#include <cstring>

/************ trie树 ***********/
// 高效存储和查找字符串。
/*
// son[父亲的位置][儿子的名字] = 儿子的位置
const int N = 1e5 + 10;
int son[N][26], idx = 1;
int cnt[N];
void insert(string &x)
{
    int p = 0;
    for (auto &e : x)
    {
        int u = e - 'a';
        if (!son[p][u])
            son[p][u] = idx++;
        p = son[p][u];
    }
    cnt[p]++;
}
int find(string &x)
{
    int p = 0;
    for (auto &e : x)
    {
        if (!son[p][e - 'a'])
            return 0;
        p = son[p][e - 'a'];
    }
    return cnt[p];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    char op;
    string x;
    while (n--)
    {
        cin >> op >> x;
        if (op == 'I')
        {
            insert(x);
        }
        else
            cout << find(x) << endl;
    }
    return 0;
}*/

/*********** 并查集 **********/
// 合并集合，查询是否在同一个集合
// 判断树根：考虑到数组下标是0~n，可以用 负数 表示到达根节点。同时-i表示这个树共有i个节点。
//
/*
const int N = 1e5 + 10;
int p[N];

// 返回x的祖宗节点
int find(int x)
{
    // p[x] < 0，表明当前x就是树跟
    if (p[x] < 0)
        return x;
    // x不是树根，找x的祖先 就相当于 找x的父亲的祖先
    return p[x] = find(p[x]);
}

// 迭代版
//  int find(int x)
//  {
//      int r = x;
//      while(p[r] >= 0)
//          r = p[r];
//      while(x != r)
//      {
//          int pp = p[x];
//          p[x] = r;
//          x = pp;
//      }
//      return r;
//  }

// 合并两个集合
void merge(int x, int y)
{
    int i = find(x), j = find(y);
    if(i != j)
        p[i] = j;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    memset(p, -1, sizeof p);
    char op;
    int a, b;
    while (m--)
    {
        scanf(" %c %d %d", &op, &a, &b);
        int i = find(a), j = find(b);
        if (op == 'M')
        {
            if (i != j)
            {
                p[i] += p[j];
                p[j] = i;
            }
        }
        else
        {
            if (i == j)
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}*/

/*********** 堆 **********/
// 堆排序
/*
const int N = 1e5 + 10;
int h[N], sz;    // sz表示堆尾
void down(int i) // logN
{
    int l = 2 * i + 1;
    if (l >= sz)
        return;
    if (l + 1 < sz && h[l + 1] < h[l])
        ++l;
    if (h[i] > h[l])
    {
        swap(h[i], h[l]);
        down(l);
    }
}

void up(int i) // 小堆
{
    if (i == 0)
        return;
    int p = (i - 1) / 2;
    if (h[p] > h[i])
    {
        swap(h[p], h[i]);
        up(p);
    }
}

// 非递归down
//  void down(int p)
//  {
//      int l = 2*p + 1;
//      while(l < sz)
//      {
//          if(l + 1 < sz && h[l + 1] < h[l]) ++l;
//          if(h[p] > h[l])
//          {
//              swap(h[p], h[l]);
//              p = l;
//              l = 2*p + 1;
//          }
//          else
//              break;
//      }
//  }
//
// 非递归up
// void up(int i)
// {
//     while (i > 0 && h[(i - 1) / 2] > h[i])
//     {
//         swap(h[(i - 1) / 2], h[i]);
//         i = (i - 1) / 2;
//     }
// }

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    sz = n;
    for (int i = 0; i < n; ++i)
        scanf("%d", h + i);

    // // 向上调整建堆竟然没超时！！！
    // for (int i = 1; i < sz; ++i)
    //     up(i);

    // 向下调整，从最后一个非叶子节点开始. O(N)
    for (int i = (n - 2) / 2; i >= 0; --i)
        down(i);
    for (int i = 0; i < m; ++i)
    {
        printf("%d ", h[0]);
        swap(h[0], h[--sz]);
        // h[0] = h[--sz];
        down(0);
    }
    return 0;
}*/
/*补：
高度为h的完全二叉树
每层节点个数为：2^(i-1)
1~i层节点总数为：2^i - 1
第i+1层有2^i个节点，比1~i总结点多了1个
*/

/*************** 进阶堆（可删除第k个插入的元素） ************/
const int N = 1e5 + 10;
// h是堆, idx是堆的容量；ph[k] 表示第k个插入元素在堆中的下标；hp[i] 表示堆中第i个元素对应第hp[i]个插入的元素
int h[N], ph[N], hp[N], idx = 1;

void h_swap(int i, int j)
{
    swap(h[i], h[j]);
    swap(ph[hp[i]], ph[hp[j]]);
    swap(hp[i], hp[j]);
}
void down(int i)
{
    int l = 2 * i;
    if (l >= idx)
        return;
    if (l + 1 < idx && h[l + 1] < h[l])
        ++l;
    if (h[i] > h[l])
    {
        h_swap(i, l);
        down(l);
    }
}

void up(int i)
{
    if (i <= 1)
        return;
    int p = i / 2;
    if (h[p] > h[i])
    {
        h_swap(p, i);
        up(p);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    char op[3];
    int k, x;
    int m = 1; // 表示用到第几个数了。只增不减
    while (n--)
    {
        scanf("%s", op);
        if (op[0] == 'I')
        {
            scanf("%d", &x);
            h[idx] = x;
            ph[m] = idx;
            hp[idx] = m;
            ++idx, ++m;
            up(idx - 1);
        }
        // 输出最小值
        else if (op[0] == 'P')
        {
            printf("%d\n", h[1]);
        }
        // 删除最小值
        else if (op[0] == 'D' && op[1] == 'M')
        {
            // 注：库里面的模板swap不能这样写：swap(1, --idx)。第一个参数是int，第二个是int&。无法匹配
            h_swap(1, --idx);
            down(1);
        }
        // 删除第k个插入的元素
        else if (op[0] == 'D')
        {
            scanf("%d", &k);
            // 下面这样写会出bug
            //  h_swap(ph[k], --idx);
            //  down(ph[k]);
            //  up(ph[k]);
            k = ph[k];
            h_swap(k, --idx);
            down(k);
            up(k);
        }
        // 修改第k个插入的元素为x
        else
        {
            scanf("%d %d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k);
            up(k);
        }
    }
}

/*作业：
143最大异或树
240食物链

// 食物链 https://www.acwing.com/problem/content/242/
#include<iostream>
#include<cstring>
using namespace std;

const int N = 50010;
int p[150010], n, k; // 开三倍。i+n表示i的食物，i+2n表示i的敌人

int find(int x)
{
    if(p[x] == -1) 
        return x;
    return p[x] = find(p[x]);
}
void merge(int x, int y)
{
    int i = find(x), j = find(y);
    if(i != j)
        p[i] = j;
}
int main()
{
    cin >> n >> k;
    memset(p, -1, sizeof p);
    int op, x, y, ret = 0;
    while(k--)
    {
        cin >> op >> x >> y;
        if(x > n || y > n)
        {
            ++ret;
            continue;
        }
        
        int xFood = find(x + n), xEnemy = find(x + 2 * n);
        int yFood = find(y + n), yEnemy = find(y + 2 * n);
        x = find(x), y = find(y);
        
        if(op == 1) // x与y是同类
        {
            // 若x是y的食物或者x是y的敌人，说明在说谎
            if(x == yFood || x == yEnemy)
                ++ret;
            else
            {
                // // 将y与x合并，y的食物与x的食物合并，y的敌人和x的敌人合并
                // p[y] = x;
                // p[yFood] = xFood;
                // p[yEnemy] = xEnemy;
                merge(y, x);
                merge(yFood, xFood);
                merge(yEnemy, xEnemy);
            }
        }
        else  // x吃y
        {
            // 若x与y的同类 或者 y吃x 即x是y的食物，说明在说谎
            if(x == y || x == yFood) 
                ++ret;
            else
            {
                // // y是x的食物，y的食物是x的敌人，y的敌人是x
                // p[y] = xFood;
                // p[yFood] = xEnemy;
                // p[yEnemy] = x;
                merge(y, xFood);
                merge(yFood, xEnemy);
                merge(yEnemy, x);
            }
        }
    }
    cout << ret;
    return 0;
}
*/